package com.hy;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:128. 最长连续序列
 * <p>
 * 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
 * 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
 *
 * 示例 1：
 * 输入：nums = [100,4,200,1,3,2]
 * 输出：4
 * 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
 * 示例 2：
 * 输入：nums = [0,3,7,2,5,8,4,6,0,1]
 * 输出：9
 * User:Mr.Du
 * Date:2024/6/12
 * Time:11:05
 */
public class LongestConsecutive {

    Map<Integer, Integer> roots = new HashMap<>();
    Map<Integer, Integer> sizes = new HashMap<>();
    /**
     * 计算给定数组中最长的连续子序列的长度。
     * 使用并查集数据结构来处理元素之间的连接关系，通过遍历数组两次来建立并查集，并计算最长子序列的长度。
     *
     * @param nums 输入的整数数组，其中包含可能包含重复元素和零的整数。
     * @return 返回数组中最长连续子序列的长度。
     */
    public int longestConsecutive(int[] nums) {
        /* 数组长度 */
        int n = nums.length;
        /* 最长连续子序列的长度 */
        int res = 0;

        /* 初始化并查集，将每个元素作为一个单独的集合 */
        for(int i : nums){
            roots.put(i, i);
            sizes.put(i, 1);
        }

        /* 遍历数组，尝试连接每个元素与其后继元素 */
        for(int i : nums){
            if(roots.containsKey(i + 1)){
                this.union(i, i + 1);
            }
        }

        /* 遍历数组，找出并查集中最大的集合大小，即最长连续子序列的长度 */
        for(int i : nums){
            if(sizes.get(i) != null)
                res = Math.max(res, sizes.get(i));
        }

        /* 返回最长连续子序列的长度 */
        return res;
    }


    /**
     * 查找并缩合并查找到的根节点。
     *
     * 该方法实现了并查集的查找操作，也称为“根查找”或“路径压缩”。
     * 它的目的是找到给定元素x所属的集合的根节点，并在查找过程中优化结构，减少后续查找的时间。
     *
     * @param x 要查找的元素
     * @return 元素x所属集合的根节点
     */
    public int find(int x){
        // 如果x就是自己的根节点，则直接返回x
        if(x == roots.get(x)) return x;
        // 否则，递归查找x的根节点，并将x直接指向它的根节点，以减少后续查找的深度
        roots.put(x, find(roots.get(x)));
        return roots.get(x);
    }


    /**
     * 将两个元素所在的集合合并为一个集合。
     *
     * 此方法用于并查集数据结构中，通过查找两个元素的根节点，并将其中一个根节点指向另一个根节点，
     * 从而合并两个集合。如果两个元素已经在同一个集合中，则不进行任何操作。
     *
     * @param i 第一个元素的索引
     * @param j 第二个元素的索引
     */
    public void union(int i, int j){
        // 分别查找元素i和j的根节点
        int x = find(i);
        int y = find(j);
        // 如果元素i和j的根节点不同，才进行合并操作
        if(x != y){
            roots.put(x, y);
            // 合并集合时，将小集合的大小加到大集合的大小上
            sizes.put(y, sizes.get(y) + sizes.get(x));
        }
    }



    /**
     * 计算给定数组中由1组成的最长连续子序列的长度。
     * 首先对数组进行排序，以便通过比较相邻元素来找出连续序列。
     */
    public int longestConsecutive1(int[] nums) {
        // 数组长度
        int n = nums.length, res = 1, cnt = 1;

        // 对数组进行排序，以便后续比较相邻元素
        Arrays.sort(nums);

        // 遍历数组，寻找最长连续序列
        for(int i = 1;i < n;i++){
            // 如果当前元素与前一个元素连续，则增加当前序列长度
            if(nums[i] == nums[i - 1]+1){
                cnt++;
                // 更新最长序列长度
                res = Math.max(res, cnt);
            }else if(nums[i] == nums[i - 1]){
                // 如果当前元素与前一个元素相同，则继续遍历
                continue;
            }else{
                // 如果当前元素与前一个元素不连续，则重置当前序列长度
                cnt = 1;
            }
        }
        // 返回最长连续1序列的长度
        return res;
    }

}
